package 复原IP地址;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/15 10:31
 * @description: 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
 */
public class Solution {
    public List<String> restoreIpAddresses(String s) {
        // 切割问题就是组会问题：采用回溯法
        // 回溯的参数：str，
        // 回溯的返回值：void
        // 回溯的终止条件：path.length == 4 Or startIndex > s.length
        // 单层回溯的逻辑：
        // 横向遍历采用 for 循环，每一次都将串s的切割位置往后移动一，避免重复
        // 纵向遍历就是切割的字串范围，需要确保树层之间不重复切割，也就需要保证范围是 startIndex 到 i（i从startIndex递增），下一次切割的位置是 stattIndex + i
        // 只要字串满足整数在 0-255 且 不含有前导0，那么他就是一个合法的 IP 地址的一部分

        backtarcking(s, 0);
        return result;
    }

    List<String> result = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public void backtarcking(String s, int startIndex) {
        if (path.size() == 4 && startIndex >= s.length()) {
            String ipStr = String.join(".", path);
            result.add(ipStr);
            return;
        }

        // 剪枝
        //  i 的范围是 startIndex 到 startIndex + 3 （因为不可能每个部分都需要满足前导非0且是0-255的数字）
        for (int i = startIndex; i < startIndex + 3 && i < s.length() && path.size() < 4; i++) {
            if (check(s, startIndex, i + 1)) {
                path.add(s.substring(startIndex, i + 1));
//                System.out.println("切割：" + s.substring(startIndex, i + 1));
//                System.out.println(">>>>>>>>>>>>>>>" + path);
                backtarcking(s, i + 1);
            } else {
                continue;
            }
            String remove = path.remove(path.size() - 1);
//            System.out.println("回溯：" + remove);
        }
    }

    // 左闭右开
    public boolean check(String s, int start, int end) {
        String substring = s.substring(start, end);
        // 不能含有前导 0
        if (substring.charAt(0) == '0') {
            if (substring.length() == 1) {
                return true;
            } else {
                return false;
            }
        }
        // 整数位于 0 到 255 之间
        int number = 0;
        for (int i = 0; i < substring.length(); i++) {
            // 段位里有非正整数字符不合法
            char c = substring.charAt(i);
            if (c >= '0' && c <= '9') {
                int num = c - '0';
                number = number * 10 + num;
            } else {
                return false;
            }
        }
        return number <= 255;
    }
}
